﻿#pragma once
#include "Index.h"

/**
 * 矩阵中的路径.
 * https://www.nowcoder.com/practice/2a49359695a544b8939c77358d29b7e6?tpId=265&tqId=39216&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D13&difficulty=undefined&judgeStatus=undefined&tags=&title=
 *
 * 请设计一个函数，用来判断在一个n乘m的矩阵中是否存在一条包含某长度为len的字符串所有字符的路径。
 * 路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
 * 如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 
 * 数据范围：0≤n,m≤20,1≤len≤25
 */
namespace StringPathInMatrix
{
	class Question
	{
	public:
		virtual bool wordPuzzle(std::vector<std::vector<char>>& grid, std::string target) = 0;
	};

	class DFS:public Question
	{
	public:
		bool wordPuzzle(std::vector<std::vector<char>>& grid, std::string target) override
		{
			if(grid.empty() || grid.front().empty() || target.empty())
				return false;

			row_count=grid.size();
			col_count=grid.front().size();

			for(int i=0;i<row_count;++i)
			{
				for(int j=0;j<col_count;++j)
				{
					if(grid[i][j]==target.front()
						&& containsPath(grid,i,j,target,0))
					{
						return true;
					}
				}
			}
			return false;
		}
	private:
		int row_count,col_count;
		std::unordered_set<int> used_grids;

		int posToKey(int x,int y)
		{
			return x*1000+y;
		}
		void keyToPos(int key,int& x,int& y)
		{
			x=key/1000;
			y=key%1000;
		}
		bool containsPath(std::vector<std::vector<char>>& grid,int x,int y,const std::string& target,int targe_index)
		{
			if(targe_index>=target.size())
				return true;
			//越界检查
			if(x<0 || x>=row_count)
				return false;
			if(y<0 || y>=col_count)
				return false;
			//值不匹配
			if(grid[x][y]!=target[targe_index])
				return false;
			//位置已被占用
			const int pos_key=posToKey(x,y);
			if(used_grids.count(pos_key))
				return false;

			//继续沿4个方向匹配下一个字符
			used_grids.insert(pos_key);
			bool contains=false;
			contains = contains || containsPath(grid,x+1,y,target,targe_index+1);
			contains = contains || containsPath(grid,x-1,y,target,targe_index+1);
			contains = contains || containsPath(grid,x,y+1,target,targe_index+1);
			contains = contains || containsPath(grid,x,y-1,target,targe_index+1);
			used_grids.erase(pos_key);

			return contains;
		}
	};
}